package reviewAlgorithms.tree;

public class LowestCommonAncestor2 {
    public static void main(String[] args) {
        System.out.println(Integer.parseInt("1"));
    }
    TreeNode res = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null){
            return null;
        }
        int h = p.val;
        int l = q.val;
        if (p.val < q.val){
            h = q.val;
            l = p.val;
        }
        getRes(root,l,h);
        return res;
    }

    private int getRes(TreeNode root, int l, int h) {
        if (root == null){
            return 0;
        }
        int left = 0;
        int right = 0;
        int current = 0;
        if (root.left != null){
            left = getRes(root.left,l,h);
        }
        if (root.right != null){
            right = getRes(root.right,l,h);
        }
        if (root.val == l || root.val == h){
            current = 1;
        }
        if (left + right + current == 2 && left <= 1 && right <= 1){
            res = root;
        }
        return left + right + current;
    }
}
